Estas notas estan basadas en el libro R for Data Science de Garrett Grolemund y Hadley Wickham

Modelo Lineal: Enfoque de Machine Learning

library(tidyverse)
library(modelr)
library(plotly)
options(na.action = na.warn)

En el contexto del curso se observa el enfoque estadístico para hallar las estimaciones de los parámetros en un modelo lineal. Obtenemos los valores con las siguientes fórmulas:

\(\hat{\beta_0} = \overline{Y} - \hat{\beta_1} \cdot \overline{X}\)

\(\hat{\beta_1} = \frac{\sum{(X_i - \overline{X})(Y_i - \overline{Y})}}{\sum{(X_i - \overline{X})^2}}\)

En este caso vamos a desarrollar otra manera de hallar los valores de estos parámetros, mediante un enfoque de optimización.

datos sim1

El paquete modlr viene con un set de datos de juguete llamado sim1

ggplot(sim1, aes(x, y)) + 
  geom_point() +
  theme_bw()

Se puede ver un patrón fuerte en los datos. Pareciera que el modelo lineal y = a_0 + a_1 * x puede ser apropiado para modelar estos datos

Modelos al azar

Para empezar, generemos aleatoriamente varios modelos lineales para ver qué forma tienen. Para eso, podemos usar geom_abline () que toma una pendiente e intercepto como parámetros.

models <- tibble(
  a1 = runif(250, -20, 40), # Función para tomar valores al azar de una distribución uniforme
  a2 = runif(250, -5, 5) # Función para tomar valores al azar de una distribución uniforme
)

ggplot(sim1, aes(x, y)) + 
  geom_abline(aes(intercept = a1, slope = a2), data = models, alpha = 1/4) +
  geom_point() +
  theme_bw()

A simple vista podemos apreciar que algunos modelos son mejores que otros. Pero necesitamos una forma de cuantificar cuales son los mejores modelos.

Distancias

Una forma de definir mejor es pensar en aquel modelo que minimiza la distancia vertical de la recta (el modelo) con cada punto:

Para eso, elijamos un modelo cualquiera:

\[ y= 7 + 1.5*x\] Y lo representamos gráficamente

dist1 <- sim1 %>% 
  mutate(
    dodge = rep(c(-1, 0, 1) / 20, 10),
    x1 = x + dodge, # para que se vean mejor las distancias, corremos un poquito cada punto sobre el eje x
    pred = 7 + x1 * 1.5
  )

ggplot(dist1, aes(x1, y)) + 
  geom_abline(intercept = 7, slope = 1.5, colour = "grey40") +
  geom_point(colour = "grey40") +
  geom_linerange(aes(ymin = y, ymax = pred), colour = "#3366FF") +
  theme_bw()

La distancia de cada punto a la recta es la diferencia entre lo que predice nuestro modelo y el valor real

Función de Modelo

Para computar la distancia, primero necesitamos una función que permita representar a cualquier modelo lineal simple. Creamos una una función que recibe un vector con los parametros del modelo, y el set de datos, y genera la predicción:

model1 <- function(ordenada, pendiente, data) {
   ordenada + data$x * pendiente
   }
model1(7, 1.5, sim1)
 [1]  8.5  8.5  8.5 10.0 10.0 10.0 11.5 11.5 11.5 13.0 13.0 13.0 14.5 14.5 14.5 16.0 16.0 16.0 17.5 17.5 17.5 19.0 19.0 19.0
[25] 20.5 20.5 20.5 22.0 22.0 22.0

Necesitamos una forma de cuantificar el error de predicción de nuestro modelo en todas las observaciones y resumirlo en única métrica. Esta será la función objetivo que buscaremos minimizar.

Una de las formas de hacerlo es con el error cuadrático medio (ECM)

\[ECM = \frac{\sum_i^n{(\hat{y_i} - y_i)^2}}{n}\]

# Creamos una función que recibe un vector con los parametros del modelo y el set de datos y devuelve el ECM
measure_distance <- function(ordenada, pendiente, data) {
 diff <- data$y - model1(ordenada, pendiente, data)
 mean(diff ^ 2)
   }
measure_distance(7, 1.5, sim1)
[1] 7.103355

Evaluando los modelos aleatorios

Ahora podemos calcular el ECM para todos los modelos del dataframe models. Para eso utilizamos el paquete purrr, para ejecutar varias veces la misma función sobre varios elementos.

MAP

Nosotros tenemos que pasar pasar los valores de a1 y a2 (dos parámetros –> map2), pero como nuestra función toma sólo uno (el vector a), nos armamos una función de ayuda para wrapear a1 y a2

# Calculamos las distancias para los nuevos modelos
models <- models %>% 
  mutate(dist = purrr::map2_dbl(a1, a2, measure_distance, sim1))
models

A continuación, superpongamos los 10 mejores modelos a los datos. Coloreamos los modelos por -dist: esta es una manera fácil de asegurarse de que los mejores modelos (es decir, los que tienen la menor distancia) obtengan los colores más brillantes.

ggplot(sim1, aes(x, y)) + 
  geom_point(size = 2, colour = "grey30") + 
  geom_abline(data = filter(models, rank(dist) <= 10),
              aes(intercept = a1, slope = a2, colour = -dist)) +
  theme_bw()

NA

También podemos pensar en estos modelos como observaciones y visualizar con un gráfico de dispersión de a1 vsa2, nuevamente coloreado por -dist. Ya no podemos ver directamente cómo se compara el modelo con los datos, pero podemos ver muchos modelos a la vez. Nuevamente, destacamos los 10 mejores modelos, esta vez dibujando círculos rojos debajo de ellos.

ggplot(models, aes(a1, a2)) +
  geom_point(data = filter(models, rank(dist) <= 10), size = 4, colour = "red") +
  geom_point(aes(colour = -dist))  +
  theme_bw()

Superficie del ECM

Podemos pasar del gráfico de la grilla de puntos a graficar los mismos datos en tres dimensiones. En el plano xy tendremos a ambos parámetros y en el eje z observamos el valor del del error cuadractico medio (ECM).

Notemos que ya no estamos trabajando con la distancia sino que estamos graficando la superficie del ECM como función de ambos parametros.

Por la fórmula del ECM esta superficie es convexa y presenta un mínimo global.

# Matriz para el grafico
rss_matrix <- matrix(models_grid[["dist"]],nrow = length(b1),ncol = length(b1), byrow = TRUE)

# Grafico usando plotly
rss_graph = plot_ly(x=b0, y=b1, z=rss_matrix) %>% add_surface(contours = list(
  z = list(
    show=TRUE,
    usecolormap=TRUE,
    highlightcolor="#ff0000",
    project=list(z=TRUE)
  )
), reversescale=TRUE)  %>%
  layout(
    title = "Superficie del ECM",
    scene = list(
      xaxis = list(title = "a0"),
      yaxis = list(title = "a1"),
      zaxis = list(title = "RSS")
    ))

rss_graph

Óptimo por métodos numéricos

Podríamos ir haciendo la cuadrícula más fina y fina hasta que nos centramos en el mejor modelo. Pero hay mejores formas de abordar ese problema como herramientas de optimización numéricas. Algunas de ellas son:

  • Método Nelder-Mead
  • Búsqueda Newton-Raphson.
  • Gradient Descent

La intuición de este último método es bastante simple: Se elige un punto de partida en la superficie de la función objetivo y se busca la pendiente más inclinada. Luego, desciende por esa pendiente un poco, y se repite una y otra vez, hasta alcanzar la condición de corte.

En R, podemos utilizar la función optim (). Cuenta con los siguientes parámetros:

  • par: vector de puntos iniciales. Elegimos el origen por poner cualquier cosa
  • fn: función objetivo, y los parámetros que nuestra función necesita (data)
# Adaptamos la función del ECM para usarla con la optimizacion
measure_distance_opt <- function(params, data) {
 diff <- data$y - model1(params[1], params[2], data)
 mean(diff ^ 2)
   }

# Corremos la optimizacion
best <- optim(c(0, 0), measure_distance_opt, data = sim1)

best
$par
[1] 4.222248 2.051204

$value
[1] 4.529154

$counts
function gradient 
      77       NA 

$convergence
[1] 0

$message
NULL
# Obtenemos los mejores parametros
best$par
[1] 4.222248 2.051204
# Graficamos la linea de los mejores parametros
ggplot(sim1, aes(x, y)) + 
  geom_point(size = 2, colour = "grey30") + 
  geom_abline(intercept = best$par[1], slope = best$par[2], color="firebrick") +
  theme_bw()

Para llegar a este resultado definimos:

  • Tipo de modelo: consideramos que nuestro conjunto de datos (fenómeno) se puede modelar con una regresión lineal simple
  • Función de costo: utilizamos el error cuadrático medio
  • Método de optimización: la función optim() usa por default el método Nelder-Mead

Función lm()

Al comparar el valor de los parámetros obtenidos mediante el método de optimización con los coeficientes estimados por la función de modelo lineal, observamos que son los mismos.

summary(lm(y~x, data=sim1))

Call:
lm(formula = y ~ x, data = sim1)

Residuals:
    Min      1Q  Median      3Q     Max 
-4.1469 -1.5197  0.1331  1.4670  4.6516 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)   4.2208     0.8688   4.858 4.09e-05 ***
x             2.0515     0.1400  14.651 1.17e-14 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.203 on 28 degrees of freedom
Multiple R-squared:  0.8846,    Adjusted R-squared:  0.8805 
F-statistic: 214.7 on 1 and 28 DF,  p-value: 1.173e-14

Nota técnica La función lm() llama a la función lm.fit(), la cual utiliza factorización o descomposición QR para resolver las ecuaciones del modelo lineal.

LS0tCnRpdGxlOiAiUmVncmVzacOzbiBMaW5lYWwgU2ltcGxlOiBFbmZvcXVlIE1hY2hpbmUgTGVhcm5pbmciCmF1dGhvcjogIkp1YW4gQmFycmlvbGEgeSBTb2bDrWEgUGVyaW5pIgpkYXRlOiAiMjUgZGUgU2VwdGllbWJyZSBkZSAyMDIxIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIHRoZW1lOiBzcGFjZWxhYgogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogeWVzCiAgICBkZl9wcmludDogcGFnZWQKLS0tCgpFc3RhcyBub3RhcyBlc3RhbiBiYXNhZGFzIGVuIGVsIGxpYnJvIFtSIGZvciBEYXRhIFNjaWVuY2VdKGh0dHA6Ly9yNGRzLmhhZC5jby5ueikgZGUgR2FycmV0dCBHcm9sZW11bmQgeSBIYWRsZXkgV2lja2hhbQoKIyBNb2RlbG8gTGluZWFsOiBFbmZvcXVlIGRlIE1hY2hpbmUgTGVhcm5pbmcKCmBgYHtyIHNldHVwLCBtZXNzYWdlID0gRkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KG1vZGVscikKbGlicmFyeShwbG90bHkpCm9wdGlvbnMobmEuYWN0aW9uID0gbmEud2FybikKYGBgCgpFbiBlbCBjb250ZXh0byBkZWwgY3Vyc28gc2Ugb2JzZXJ2YSBlbCBlbmZvcXVlICoqZXN0YWTDrXN0aWNvKiogcGFyYSBoYWxsYXIgbGFzIGVzdGltYWNpb25lcyBkZSBsb3MgcGFyw6FtZXRyb3MgZW4gdW4gbW9kZWxvIGxpbmVhbC4gT2J0ZW5lbW9zIGxvcyB2YWxvcmVzIGNvbiBsYXMgc2lndWllbnRlcyBmw7NybXVsYXM6CgokXGhhdHtcYmV0YV8wfSA9IFxvdmVybGluZXtZfSAtIFxoYXR7XGJldGFfMX0gXGNkb3QgXG92ZXJsaW5le1h9JAoKJFxoYXR7XGJldGFfMX0gPSBcZnJhY3tcc3VteyhYX2kgLSBcb3ZlcmxpbmV7WH0pKFlfaSAtIFxvdmVybGluZXtZfSl9fXtcc3VteyhYX2kgLSBcb3ZlcmxpbmV7WH0pXjJ9fSQKCkVuIGVzdGUgY2FzbyB2YW1vcyBhIGRlc2Fycm9sbGFyIG90cmEgbWFuZXJhIGRlIGhhbGxhciBsb3MgdmFsb3JlcyBkZSBlc3RvcyBwYXLDoW1ldHJvcywgbWVkaWFudGUgdW4gZW5mb3F1ZSBkZSBvcHRpbWl6YWNpw7NuLgoKIyMgZGF0b3Mgc2ltMQoKRWwgcGFxdWV0ZSBtb2RsciB2aWVuZSBjb24gdW4gc2V0IGRlIGRhdG9zIGRlIGp1Z3VldGUgbGxhbWFkbyBzaW0xCgpgYGB7cn0KZ2dwbG90KHNpbTEsIGFlcyh4LCB5KSkgKyAKICBnZW9tX3BvaW50KCkgKwogIHRoZW1lX2J3KCkKYGBgCgpTZSBwdWVkZSB2ZXIgdW4gcGF0csOzbiBmdWVydGUgZW4gbG9zIGRhdG9zLiBQYXJlY2llcmEgcXVlIGVsIG1vZGVsbyBsaW5lYWwgYHkgPSBhXzAgKyBhXzEgKiB4YCBwdWVkZSBzZXIgYXByb3BpYWRvIHBhcmEgbW9kZWxhciBlc3RvcyBkYXRvcyAKCiMjIE1vZGVsb3MgYWwgYXphcgoKUGFyYSBlbXBlemFyLCBnZW5lcmVtb3MgYWxlYXRvcmlhbWVudGUgdmFyaW9zIG1vZGVsb3MgbGluZWFsZXMgcGFyYSB2ZXIgcXXDqSBmb3JtYSB0aWVuZW4uIFBhcmEgZXNvLCBwb2RlbW9zIHVzYXIgYGdlb21fYWJsaW5lICgpYCBxdWUgdG9tYSB1bmEgcGVuZGllbnRlIGUgaW50ZXJjZXB0byBjb21vIHBhcsOhbWV0cm9zLiAKCmBgYHtyfQptb2RlbHMgPC0gdGliYmxlKAogIGExID0gcnVuaWYoMjUwLCAtMjAsIDQwKSwgIyBGdW5jacOzbiBwYXJhIHRvbWFyIHZhbG9yZXMgYWwgYXphciBkZSB1bmEgZGlzdHJpYnVjacOzbiB1bmlmb3JtZQogIGEyID0gcnVuaWYoMjUwLCAtNSwgNSkgIyBGdW5jacOzbiBwYXJhIHRvbWFyIHZhbG9yZXMgYWwgYXphciBkZSB1bmEgZGlzdHJpYnVjacOzbiB1bmlmb3JtZQopCgpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fYWJsaW5lKGFlcyhpbnRlcmNlcHQgPSBhMSwgc2xvcGUgPSBhMiksIGRhdGEgPSBtb2RlbHMsIGFscGhhID0gMS80KSArCiAgZ2VvbV9wb2ludCgpICsKICB0aGVtZV9idygpCmBgYAoKQSBzaW1wbGUgdmlzdGEgcG9kZW1vcyBhcHJlY2lhciBxdWUgYWxndW5vcyBtb2RlbG9zIHNvbiBtZWpvcmVzIHF1ZSBvdHJvcy4gUGVybyBuZWNlc2l0YW1vcyB1bmEgZm9ybWEgZGUgY3VhbnRpZmljYXIgY3VhbGVzIHNvbiBsb3MgX21lam9yZXNfIG1vZGVsb3MuIAoKIyMgRGlzdGFuY2lhcwoKVW5hIGZvcm1hIGRlIGRlZmluaXIgX21lam9yXyBlcyBwZW5zYXIgZW4gYXF1ZWwgbW9kZWxvIHF1ZSBtaW5pbWl6YSBsYSBkaXN0YW5jaWEgdmVydGljYWwgZGUgbGEgcmVjdGEgKGVsIG1vZGVsbykgY29uIGNhZGEgcHVudG86CgpQYXJhIGVzbywgZWxpamFtb3MgdW4gbW9kZWxvIGN1YWxxdWllcmE6CgokJCB5PSA3ICsgMS41KngkJApZIGxvIHJlcHJlc2VudGFtb3MgZ3LDoWZpY2FtZW50ZQoKYGBge3J9CmRpc3QxIDwtIHNpbTEgJT4lIAogIG11dGF0ZSgKICAgIGRvZGdlID0gcmVwKGMoLTEsIDAsIDEpIC8gMjAsIDEwKSwKICAgIHgxID0geCArIGRvZGdlLCAjIHBhcmEgcXVlIHNlIHZlYW4gbWVqb3IgbGFzIGRpc3RhbmNpYXMsIGNvcnJlbW9zIHVuIHBvcXVpdG8gY2FkYSBwdW50byBzb2JyZSBlbCBlamUgeAogICAgcHJlZCA9IDcgKyB4MSAqIDEuNQogICkKCmdncGxvdChkaXN0MSwgYWVzKHgxLCB5KSkgKyAKICBnZW9tX2FibGluZShpbnRlcmNlcHQgPSA3LCBzbG9wZSA9IDEuNSwgY29sb3VyID0gImdyZXk0MCIpICsKICBnZW9tX3BvaW50KGNvbG91ciA9ICJncmV5NDAiKSArCiAgZ2VvbV9saW5lcmFuZ2UoYWVzKHltaW4gPSB5LCB5bWF4ID0gcHJlZCksIGNvbG91ciA9ICIjMzM2NkZGIikgKwogIHRoZW1lX2J3KCkKYGBgCgoKTGEgZGlzdGFuY2lhIGRlIGNhZGEgcHVudG8gYSBsYSByZWN0YSBlcyBsYSBkaWZlcmVuY2lhIGVudHJlIGxvIHF1ZSBwcmVkaWNlIG51ZXN0cm8gbW9kZWxvIHkgZWwgdmFsb3IgcmVhbAoKIyMgRnVuY2nDs24gZGUgTW9kZWxvCgpQYXJhIGNvbXB1dGFyIGxhIGRpc3RhbmNpYSwgcHJpbWVybyBuZWNlc2l0YW1vcyB1bmEgZnVuY2nDs24gcXVlIHBlcm1pdGEgcmVwcmVzZW50YXIgYSBjdWFscXVpZXIgbW9kZWxvIGxpbmVhbCBzaW1wbGUuIENyZWFtb3MgdW5hICB1bmEgZnVuY2nDs24gcXVlIHJlY2liZSB1biB2ZWN0b3IgY29uIGxvcyBwYXJhbWV0cm9zIGRlbCBtb2RlbG8sIHkgZWwgc2V0IGRlIGRhdG9zLCB5IGdlbmVyYSBsYSBwcmVkaWNjacOzbjoKICAKYGBge3J9Cm1vZGVsMSA8LSBmdW5jdGlvbihvcmRlbmFkYSwgcGVuZGllbnRlLCBkYXRhKSB7CiAgIG9yZGVuYWRhICsgZGF0YSR4ICogcGVuZGllbnRlCiAgIH0KbW9kZWwxKDcsIDEuNSwgc2ltMSkKYGBgCgpOZWNlc2l0YW1vcyB1bmEgZm9ybWEgZGUgY3VhbnRpZmljYXIgZWwgZXJyb3IgZGUgcHJlZGljY2nDs24gZGUgbnVlc3RybyBtb2RlbG8gZW4gdG9kYXMgbGFzIG9ic2VydmFjaW9uZXMgeSByZXN1bWlybG8gZW4gw7puaWNhIG3DqXRyaWNhLgpFc3RhIHNlcsOhIGxhIGZ1bmNpw7NuIG9iamV0aXZvIHF1ZSBidXNjYXJlbW9zIG1pbmltaXphci4gCgpVbmEgZGUgbGFzIGZvcm1hcyBkZSBoYWNlcmxvIGVzIGNvbiBlbCBlcnJvciBjdWFkcsOhdGljbyBtZWRpbyAoRUNNKQoKJCRFQ00gPSBcZnJhY3tcc3VtX2lebnsoXGhhdHt5X2l9IC0geV9pKV4yfX17bn0kJAoKYGBge3J9CiMgQ3JlYW1vcyB1bmEgZnVuY2nDs24gcXVlIHJlY2liZSB1biB2ZWN0b3IgY29uIGxvcyBwYXJhbWV0cm9zIGRlbCBtb2RlbG8geSBlbCBzZXQgZGUgZGF0b3MgeSBkZXZ1ZWx2ZSBlbCBFQ00KbWVhc3VyZV9kaXN0YW5jZSA8LSBmdW5jdGlvbihvcmRlbmFkYSwgcGVuZGllbnRlLCBkYXRhKSB7CiBkaWZmIDwtIGRhdGEkeSAtIG1vZGVsMShvcmRlbmFkYSwgcGVuZGllbnRlLCBkYXRhKQogbWVhbihkaWZmIF4gMikKICAgfQptZWFzdXJlX2Rpc3RhbmNlKDcsIDEuNSwgc2ltMSkKYGBgCgojIyBFdmFsdWFuZG8gbG9zIG1vZGVsb3MgYWxlYXRvcmlvcwoKQWhvcmEgcG9kZW1vcyBjYWxjdWxhciBlbCBfX0VDTV9fIHBhcmEgdG9kb3MgbG9zIG1vZGVsb3MgZGVsIGRhdGFmcmFtZSBfbW9kZWxzXy4gUGFyYSBlc28gdXRpbGl6YW1vcyBlbCBwYXF1ZXRlIF9fcHVycnJfXywgcGFyYSBlamVjdXRhciB2YXJpYXMgdmVjZXMgbGEgbWlzbWEgZnVuY2nDs24gc29icmUgdmFyaW9zIGVsZW1lbnRvcy4gCgojIyMgTUFQCgpOb3NvdHJvcyB0ZW5lbW9zIHF1ZSBwYXNhciBwYXNhciBsb3MgdmFsb3JlcyBkZSBhMSB5IGEyIChkb3MgcGFyw6FtZXRyb3MgLS0+IG1hcDIpLCBwZXJvIGNvbW8gbnVlc3RyYSBmdW5jacOzbiB0b21hIHPDs2xvIHVubyAoZWwgdmVjdG9yIGEpLCBub3MgYXJtYW1vcyB1bmEgZnVuY2nDs24gZGUgYXl1ZGEgcGFyYSB3cmFwZWFyIGExIHkgYTIKCgpgYGB7cn0KIyBDYWxjdWxhbW9zIGxhcyBkaXN0YW5jaWFzIHBhcmEgbG9zIG51ZXZvcyBtb2RlbG9zCm1vZGVscyA8LSBtb2RlbHMgJT4lIAogIG11dGF0ZShkaXN0ID0gcHVycnI6Om1hcDJfZGJsKGExLCBhMiwgbWVhc3VyZV9kaXN0YW5jZSwgc2ltMSkpCm1vZGVscwpgYGAKCgpBIGNvbnRpbnVhY2nDs24sIHN1cGVycG9uZ2Ftb3MgbG9zIDEwIG1lam9yZXMgbW9kZWxvcyBhIGxvcyBkYXRvcy4gQ29sb3JlYW1vcyBsb3MgbW9kZWxvcyBwb3IgYC1kaXN0YDogZXN0YSBlcyB1bmEgbWFuZXJhIGbDoWNpbCBkZSBhc2VndXJhcnNlIGRlIHF1ZSBsb3MgbWVqb3JlcyBtb2RlbG9zIChlcyBkZWNpciwgbG9zIHF1ZSB0aWVuZW4gbGEgbWVub3IgZGlzdGFuY2lhKSBvYnRlbmdhbiBsb3MgY29sb3JlcyBtw6FzIGJyaWxsYW50ZXMuCgoKYGBge3J9CmdncGxvdChzaW0xLCBhZXMoeCwgeSkpICsgCiAgZ2VvbV9wb2ludChzaXplID0gMiwgY29sb3VyID0gImdyZXkzMCIpICsgCiAgZ2VvbV9hYmxpbmUoZGF0YSA9IGZpbHRlcihtb2RlbHMsIHJhbmsoZGlzdCkgPD0gMTApLAogICAgICAgICAgICAgIGFlcyhpbnRlcmNlcHQgPSBhMSwgc2xvcGUgPSBhMiwgY29sb3VyID0gLWRpc3QpKSArCiAgdGhlbWVfYncoKQogICAgICAgICAgICAgIApgYGAKClRhbWJpw6luIHBvZGVtb3MgcGVuc2FyIGVuIGVzdG9zIG1vZGVsb3MgY29tbyBvYnNlcnZhY2lvbmVzIHkgdmlzdWFsaXphciBjb24gdW4gZ3LDoWZpY28gZGUgZGlzcGVyc2nDs24gZGUgYGExYCB2c2AgYTJgLCBudWV2YW1lbnRlIGNvbG9yZWFkbyBwb3IgYC1kaXN0YC4gWWEgbm8gcG9kZW1vcyB2ZXIgZGlyZWN0YW1lbnRlIGPDs21vIHNlIGNvbXBhcmEgZWwgbW9kZWxvIGNvbiBsb3MgZGF0b3MsIHBlcm8gcG9kZW1vcyB2ZXIgbXVjaG9zIG1vZGVsb3MgYSBsYSB2ZXouIE51ZXZhbWVudGUsIGRlc3RhY2Ftb3MgbG9zIDEwIG1lam9yZXMgbW9kZWxvcywgZXN0YSB2ZXogZGlidWphbmRvIGPDrXJjdWxvcyByb2pvcyBkZWJham8gZGUgZWxsb3MuCgpgYGB7cn0KZ2dwbG90KG1vZGVscywgYWVzKGExLCBhMikpICsKICBnZW9tX3BvaW50KGRhdGEgPSBmaWx0ZXIobW9kZWxzLCByYW5rKGRpc3QpIDw9IDEwKSwgc2l6ZSA9IDQsIGNvbG91ciA9ICJyZWQiKSArCiAgZ2VvbV9wb2ludChhZXMoY29sb3VyID0gLWRpc3QpKSAgKwogIHRoZW1lX2J3KCkKYGBgCgojIyBHcmlkIHNlYXJjaAoKRW4gbHVnYXIgZGUgcHJvYmFyIG11Y2hvcyBtb2RlbG9zIGFsZWF0b3Jpb3MsIHBvZHLDrWFtb3Mgc2VyIG3DoXMgc2lzdGVtw6F0aWNvcyB5IGdlbmVyYXIgdW5hIGN1YWRyw61jdWxhIGRlIHB1bnRvcyB1bmlmb3JtZW1lbnRlIGVzcGFjaWFkYSAoZXN0byBzZSBkZW5vbWluYSBncmlkIHNlYXJjaCkuIEVsZWdpbW9zIGxvcyBwYXLDoW1ldHJvcyBkZSBsYSBncmlsbGEgYXByb3hpbWFkYW1lbnRlIG1pcmFuZG8gZMOzbmRlIGVzdGFiYW4gbG9zIG1lam9yZXMgbW9kZWxvcyBlbiBlbCBncsOhZmljbyBhbnRlcmlvci4KCgpgYGB7cn0KIyBDcmVhciBsYSBncmlsbGEKZ3JpZCA8LSBleHBhbmQuZ3JpZCgKICBhMSA9IHNlcSgtNSwgMjAsIGxlbmd0aCA9IDI1KSwKICBhMiA9IHNlcSgxLCAzLCBsZW5ndGggPSAyNSkKICApICU+JSAKICAjIENhbGN1bGFyIGxhIGRpc3RhbmNpYQogIG11dGF0ZShkaXN0ID0gcHVycnI6Om1hcDJfZGJsKGExLCBhMiwgbWVhc3VyZV9kaXN0YW5jZSwgc2ltMSkpCgpncmlkICU+JSAKICBnZ3Bsb3QoYWVzKGExLCBhMikpICsKICBnZW9tX3BvaW50KGRhdGEgPSBmaWx0ZXIoZ3JpZCwgcmFuayhkaXN0KSA8PSAxMCksIHNpemUgPSA0LCBjb2xvdXIgPSAicmVkIikgKwogIGdlb21fcG9pbnQoYWVzKGNvbG91ciA9IC1kaXN0KSkgKwogIHRoZW1lX2J3KCkKYGBgCgpDdWFuZG8gc3VwZXJwb25lbW9zIGxvcyAxMCBtZWpvcmVzIG1vZGVsb3MgZW4gbG9zIGRhdG9zIG9yaWdpbmFsZXMsIHRvZG9zIHNlIHZlbiBiYXN0YW50ZSBiaWVuOgoKYGBge3J9CmdncGxvdChzaW0xLCBhZXMoeCwgeSkpICsgCiAgZ2VvbV9wb2ludChzaXplID0gMiwgY29sb3VyID0gImdyZXkzMCIpICsgCiAgZ2VvbV9hYmxpbmUoCiAgICBhZXMoaW50ZXJjZXB0ID0gYTEsIHNsb3BlID0gYTIsIGNvbG91ciA9IC1kaXN0KSwgCiAgICBkYXRhID0gZmlsdGVyKGdyaWQsIHJhbmsoZGlzdCkgPD0gMTApKSArCiAgdGhlbWVfYncoKQpgYGAKCiMjIFN1cGVyZmljaWUgZGVsIEVDTQoKUG9kZW1vcyBwYXNhciBkZWwgZ3LDoWZpY28gZGUgbGEgZ3JpbGxhIGRlIHB1bnRvcyBhIGdyYWZpY2FyIGxvcyBtaXNtb3MgZGF0b3MgZW4gdHJlcyBkaW1lbnNpb25lcy4gRW4gZWwgcGxhbm8gKnh5KiB0ZW5kcmVtb3MgYSBhbWJvcyBwYXLDoW1ldHJvcyB5IGVuIGVsIGVqZSAqeiogb2JzZXJ2YW1vcyBlbCB2YWxvciBkZWwgZGVsIGVycm9yIGN1YWRyYWN0aWNvIG1lZGlvIChFQ00pLgoKTm90ZW1vcyBxdWUgeWEgbm8gZXN0YW1vcyB0cmFiYWphbmRvIGNvbiBsYSBkaXN0YW5jaWEgc2lubyBxdWUgZXN0YW1vcyBncmFmaWNhbmRvIGxhIHN1cGVyZmljaWUgZGVsIEVDTSBjb21vIGZ1bmNpw7NuIGRlIGFtYm9zIHBhcmFtZXRyb3MuCgpQb3IgbGEgZsOzcm11bGEgZGVsIEVDTSBlc3RhIHN1cGVyZmljaWUgZXMgY29udmV4YSB5IHByZXNlbnRhIHVuIG3DrW5pbW8gZ2xvYmFsLgoKYGBge3IsIGVjaG89RkFMU0V9CiMgTW9kZWxvIGxpbmVhbAptb2RlbF9wcmVkaWN0aW9ucyA8LSBmdW5jdGlvbihwYXJhbWV0ZXJzLCBkYXRhLCBwcmVkaWN0b3IpewogICBwcmVkIDwtIHBhcmFtZXRlcnNbMV0gKyBwYXJhbWV0ZXJzWzJdICogZGF0YVtbcHJlZGljdG9yXV0KICAgcmV0dXJuKHByZWQpCn0KCiMgQ2FsY3VsYXIgZWwgcnNzCmdldF9yc3MgPC0gZnVuY3Rpb24ocGFyYW1ldGVycywgZGF0YSwgcHJlZGljdG9yID0gJ3gnLCBwcmVkaWN0ZWQgPSAneScpewogIHByZWRpY3Rpb24gPC0gbW9kZWxfcHJlZGljdGlvbnMocGFyYW1ldGVycywgZGF0YSwgcHJlZGljdG9yID0gcHJlZGljdG9yKQogIHJlc2lkdWFscyA8LSBkYXRhW1twcmVkaWN0ZWRdXSAtIG1vZGVsX3ByZWRpY3Rpb25zKHBhcmFtZXRlcnMsIGRhdGEsICd4JykgIAogIHJzcyA8LSBzdW0oKHJlc2lkdWFscyleMikKICByZXR1cm4ocnNzKQp9CgojQ2FsY3VsYXIgZWwgcnNzIHBhcmEgZWwgZGF0YXNldCBzaW0xCnNpbTFfZ2V0X3JzcyA8LSBmdW5jdGlvbihhMCwgYTEpIHsKICBnZXRfcnNzKGMoYTAsIGExKSwgc2ltMSkKfQoKIyBWZWN0b3JlcyBkZSBwYXJhbWV0cm9zCmIwID0gc2VxKDIsIDYsIGJ5ID0gMC4xKQpiMSA9IHNlcSgxLjcsIDIuNSwgbGVuZ3RoPWxlbmd0aChiMCkpCgojIEdyaWxsYSBkZSBtb2RlbG9zCm1vZGVsc19ncmlkIDwtIGV4cGFuZC5ncmlkKAogIAogIGIwID0gc2VxKDIsIDYsIGJ5ID0gMC4xKSwKICBiMSA9IHNlcSgxLjcsIDIuNSwgbGVuZ3RoPWxlbmd0aChiMSkpCikgJT4lIAogIG11dGF0ZShkaXN0ID0gcHVycnI6Om1hcDJfZGJsKGIwLCBiMSwgc2ltMV9nZXRfcnNzKSkgCgoKYGBgCgpgYGB7cn0KIyBNYXRyaXogcGFyYSBlbCBncmFmaWNvCnJzc19tYXRyaXggPC0gbWF0cml4KG1vZGVsc19ncmlkW1siZGlzdCJdXSxucm93ID0gbGVuZ3RoKGIxKSxuY29sID0gbGVuZ3RoKGIxKSwgYnlyb3cgPSBUUlVFKQoKIyBHcmFmaWNvIHVzYW5kbyBwbG90bHkKcnNzX2dyYXBoID0gcGxvdF9seSh4PWIwLCB5PWIxLCB6PXJzc19tYXRyaXgpICU+JSBhZGRfc3VyZmFjZShjb250b3VycyA9IGxpc3QoCiAgeiA9IGxpc3QoCiAgICBzaG93PVRSVUUsCiAgICB1c2Vjb2xvcm1hcD1UUlVFLAogICAgaGlnaGxpZ2h0Y29sb3I9IiNmZjAwMDAiLAogICAgcHJvamVjdD1saXN0KHo9VFJVRSkKICApCiksIHJldmVyc2VzY2FsZT1UUlVFKSAgJT4lCiAgbGF5b3V0KAogICAgdGl0bGUgPSAiU3VwZXJmaWNpZSBkZWwgRUNNIiwKICAgIHNjZW5lID0gbGlzdCgKICAgICAgeGF4aXMgPSBsaXN0KHRpdGxlID0gImEwIiksCiAgICAgIHlheGlzID0gbGlzdCh0aXRsZSA9ICJhMSIpLAogICAgICB6YXhpcyA9IGxpc3QodGl0bGUgPSAiUlNTIikKICAgICkpCgpyc3NfZ3JhcGgKYGBgCgojIyDDk3B0aW1vIHBvciBtw6l0b2RvcyBudW3DqXJpY29zIAoKUG9kcsOtYW1vcyBpciBoYWNpZW5kbyBsYSBjdWFkcsOtY3VsYSBtw6FzIGZpbmEgeSBmaW5hIGhhc3RhIHF1ZSBub3MgY2VudHJhbW9zIGVuIGVsIG1lam9yIG1vZGVsby4gUGVybyBoYXkgbWVqb3JlcyBmb3JtYXMgZGUgYWJvcmRhciBlc2UgcHJvYmxlbWEgY29tbyBoZXJyYW1pZW50YXMgZGUgb3B0aW1pemFjacOzbiBudW3DqXJpY2FzLiBBbGd1bmFzIGRlIGVsbGFzIHNvbjoKCiogTcOpdG9kbyBOZWxkZXItTWVhZAoqIELDunNxdWVkYSBfX05ld3Rvbi1SYXBoc29uX18uCiogKipHcmFkaWVudCBEZXNjZW50KioKCkxhIGludHVpY2nDs24gZGUgZXN0ZSDDumx0aW1vIG3DqXRvZG8gZXMgYmFzdGFudGUgc2ltcGxlOiBTZSBlbGlnZSB1biBwdW50byBkZSBwYXJ0aWRhIGVuIGxhIHN1cGVyZmljaWUgZGUgbGEgZnVuY2nDs24gb2JqZXRpdm8geSBzZSBidXNjYSBsYSBwZW5kaWVudGUgbcOhcyBpbmNsaW5hZGEuIEx1ZWdvLCBkZXNjaWVuZGUgcG9yIGVzYSBwZW5kaWVudGUgdW4gcG9jbywgeSBzZSByZXBpdGUgdW5hIHkgb3RyYSB2ZXosIGhhc3RhIGFsY2FuemFyIGxhIGNvbmRpY2nDs24gZGUgY29ydGUuIAoKCkVuIFIsIHBvZGVtb3MgdXRpbGl6YXIgbGEgZnVuY2nDs24gYG9wdGltICgpYC4gQ3VlbnRhIGNvbiBsb3Mgc2lndWllbnRlcyBwYXLDoW1ldHJvczoKCi0gKipwYXIqKjogdmVjdG9yIGRlIHB1bnRvcyBpbmljaWFsZXMuIEVsZWdpbW9zIGVsIG9yaWdlbiBwb3IgcG9uZXIgY3VhbHF1aWVyIGNvc2EKLSAqKmZuKio6IGZ1bmNpw7NuIG9iamV0aXZvLCB5IGxvcyBwYXLDoW1ldHJvcyBxdWUgbnVlc3RyYSBmdW5jacOzbiBuZWNlc2l0YSAoZGF0YSkKCmBgYHtyfQojIEFkYXB0YW1vcyBsYSBmdW5jacOzbiBkZWwgRUNNIHBhcmEgdXNhcmxhIGNvbiBsYSBvcHRpbWl6YWNpb24KbWVhc3VyZV9kaXN0YW5jZV9vcHQgPC0gZnVuY3Rpb24ocGFyYW1zLCBkYXRhKSB7CiBkaWZmIDwtIGRhdGEkeSAtIG1vZGVsMShwYXJhbXNbMV0sIHBhcmFtc1syXSwgZGF0YSkKIG1lYW4oZGlmZiBeIDIpCiAgIH0KCiMgQ29ycmVtb3MgbGEgb3B0aW1pemFjaW9uCmJlc3QgPC0gb3B0aW0oYygwLCAwKSwgbWVhc3VyZV9kaXN0YW5jZV9vcHQsIGRhdGEgPSBzaW0xKQoKYmVzdApgYGAKCmBgYHtyfQojIE9idGVuZW1vcyBsb3MgbWVqb3JlcyBwYXJhbWV0cm9zCmJlc3QkcGFyCgojIEdyYWZpY2Ftb3MgbGEgbGluZWEgZGUgbG9zIG1lam9yZXMgcGFyYW1ldHJvcwpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9ICJncmV5MzAiKSArIAogIGdlb21fYWJsaW5lKGludGVyY2VwdCA9IGJlc3QkcGFyWzFdLCBzbG9wZSA9IGJlc3QkcGFyWzJdLCBjb2xvcj0iZmlyZWJyaWNrIikgKwogIHRoZW1lX2J3KCkKYGBgCgpQYXJhIGxsZWdhciBhIGVzdGUgcmVzdWx0YWRvIGRlZmluaW1vczoKCiogKipUaXBvIGRlIG1vZGVsbyoqOiBjb25zaWRlcmFtb3MgcXVlIG51ZXN0cm8gY29uanVudG8gZGUgZGF0b3MgKGZlbsOzbWVubykgc2UgcHVlZGUgbW9kZWxhciBjb24gdW5hIHJlZ3Jlc2nDs24gbGluZWFsIHNpbXBsZQoqICoqRnVuY2nDs24gZGUgY29zdG8qKjogdXRpbGl6YW1vcyBlbCBlcnJvciBjdWFkcsOhdGljbyBtZWRpbwoqICoqTcOpdG9kbyBkZSBvcHRpbWl6YWNpw7NuKio6IGxhIGZ1bmNpw7NuIGBvcHRpbSgpYCB1c2EgcG9yIGRlZmF1bHQgZWwgbcOpdG9kbyBOZWxkZXItTWVhZAoKIyMgRnVuY2nDs24gbG0oKQoKQWwgY29tcGFyYXIgZWwgdmFsb3IgZGUgbG9zIHBhcsOhbWV0cm9zIG9idGVuaWRvcyBtZWRpYW50ZSBlbCBtw6l0b2RvIGRlIG9wdGltaXphY2nDs24gY29uIGxvcyBjb2VmaWNpZW50ZXMgZXN0aW1hZG9zIHBvciBsYSBmdW5jacOzbiBkZSBtb2RlbG8gbGluZWFsLCBvYnNlcnZhbW9zIHF1ZSBzb24gbG9zIG1pc21vcy4KCmBgYHtyfQpzdW1tYXJ5KGxtKHl+eCwgZGF0YT1zaW0xKSkKYGBgCioqTm90YSB0w6ljbmljYSoqCkxhIGZ1bmNpw7NuIGBsbSgpYCBsbGFtYSBhIGxhIGZ1bmNpw7NuIGBsbS5maXQoKWAsIGxhIGN1YWwgdXRpbGl6YSAqKmZhY3Rvcml6YWNpw7NuIG8gZGVzY29tcG9zaWNpw7NuIFFSKiogcGFyYSByZXNvbHZlciBsYXMgZWN1YWNpb25lcyBkZWwgbW9kZWxvIGxpbmVhbC4KCgo=